/*
 * @lc app=leetcode id=472 lang=cpp
 *
 * [472] Concatenated Words
 */

// @lc code=start
class Solution {
public:
       vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_map<std::string, bool> table;

        int mi = 10000;
        int mx = 0;
        for (auto w : words) {
            if (w.empty()) {
              continue;
            }

            table[w] = true;
            int n = static_cast<int>(w.size());
            mi = std::min(n, mi);
            mx = std::max(n, mx);
        }
        if (mx <= mi) {
            return {};
        }
        sort(words.begin(), words.end(), [](const string &lhs, const string &rhs) {
            return lhs.size() < rhs.size();
        });
        vector<string> ans;
        for (auto w : words) {
            if (Solve(table, w, mi)) {
                ans.push_back(w);
            }
        }
        return ans;
    }
    
    bool Solve(unordered_map<string, bool> &table, std::string w, int mn) {
        if (w.size() < mn) {
            return false;
        }
        for (int i = mn; i + mn <= w.size(); ++i) {
            auto a = w.substr(0, i);
            if (table[a]) {
                auto b = w.substr(i);
                if (table[b]) {
                    return true;
                }
                if (Solve(table, b, mn)){
                    table[b] = true;
                    return true;
                }
            }
        }
        return false;        
    }


    
};
// @lc code=end

